W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Permutacja -elementowa jest ciągiem -elementowym składającym się z różnych liczb ze zbioru . Przykładowo, ciąg jest permutacją -elementową.
W permutacjach liczb będą interesować nas najdłuższe rosnące podciągi. W przykładowej permutacji mają one długość i istnieją dokładnie dwa takie podciągi, a mianowicie oraz .
Superliczbą nazwiemy każdą liczbę, która należy do dowolnego z najdłuższych rosnących podciągów. W permutacji superliczbami są , zaś liczba superliczbą nie jest.
Twoim zadaniem jest dla zadanej permutacji znaleźć wszystkie superliczby.
Napisz program, który:
Wejście składa się z dwóch wierszy. W pierwszym wierszu znajduję się jedna liczba , . W drugim wierszu znajduję się liczb tworzących permutację -elementową, pooddzielanych pojedynczymi odstępami.
Wyjście powinno się składać z dwóch wierszy. W pierwszym wierszu powinna znaleźć się jedna liczba - liczba superliczb w wejściowej permutacji. W drugim powinny znaleźć się superliczby pooddzielane pojedynczymi odstępami, wymienione w kolejności rosnącej.
Dla danych wejściowych:
5 2 1 4 5 3
poprawną odpowiedzią jest:
4 1 2 4 5
Autor zadania: Jakub Pawlewicz.